import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-10-28
 * Time: 19:44
 */

/**
 * 稳定的排序只有三个；插入排序，冒泡排序，归并排序，（计数排序）
 * 快排空间复杂度：O(LoN) 归并排序：O(N)
 */


public class Test {
    /**
     * 1.直接插入排序
     * 时间复杂度：
     *   最好的情况下：O(n)  有序排列
     *   最坏的情况下：O(n^2) 逆序排序
     *   空间复杂度：O(1)
     * 稳定性：稳定
     *      一个本身就稳定的排序可以实现为不稳定
     *      但一个本身就不稳定的排序不可能实现为稳定的排序
     * 当数据越有序的时候，直排效率越高
     */
    public static void insertSort(int[] arr){
        for  (int i = 1; i < arr.length; i++){
            int j = i - 1;
            int tmp = arr[i];
            for (;j >= 0;j--){
                if (arr[j] > tmp)
                    arr[j + 1] = arr[j];
                else
                    break;
            }
            arr[j + 1] = tmp;
        }
    }

    /**
     * 2.希尔排序
     *   时间复杂度：O(n^1.3)
     *   空间复杂度：O(1)
     *   不稳定
     */
    public static void shellSort(int[] arr){
         int gap = arr.length;
         while(gap > 1) {
             gap /= 2;
             shell(arr, gap);
         }
    }
    private static void shell(int[] arr, int gap){
        for (int i = gap; i < arr.length; i++){
            int tmp = arr[i];
            int j = i - gap;
            for (; j >= 0; j -= gap){
                if (arr[j] > tmp)
                    arr[j + gap] = arr[j];
                else
                    break;
            }
            arr[j + gap] = tmp;
        }
    }

    /**
     * 3.选择排序
     *  时间复杂度：O(n^2)
     *  空间复杂度：O(1)
     *  稳定性；不稳定
     */
    public static void selectSort(int[] arr){
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            int min = i;
            for (int j = i + 1; j < len; j++) {
                if (arr[min] > arr[j]){
                    min = j;
                }
            }
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
    public static void selectSort1(int[] arr){
        int len = arr.length;
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int min = left;
            int max = left;
            for (int i = left + 1; i <= right; i++) {
                if (arr[min] > arr[i]) {
                    min = i;
                }
                if (arr[max] < arr[i]) {
                    max = i;
                }
            }
            int tmp = arr[left];
            arr[left] = arr[min];
            arr[min] = tmp;
            if (max == left){
                max = min;
            }
            tmp = arr[right];
            arr[right] = arr[max];
            arr[max] = tmp;
            left++;
            right--;
        }
    }

    /**
     * 4.堆排序
     * 时间复杂度：O(n * logN) 对数据不敏感（不管无序还是有序都是这个表达式）
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public static void heapSort(int[] arr){
        createBigHeap(arr);
        int end = arr.length - 1;
        while (end > 0){
            int tmp = arr[0];
            arr[0] = arr[end];
            arr[end] = tmp;
            shiftDown(arr, 0, end);
            end--;
        }
    }
    private static void createBigHeap(int[] arr){
        for (int parent = (arr.length - 1 - 1) / 2; parent >= 0 ; parent--){
            shiftDown(arr, parent, arr.length);
        }
    }
    private static void shiftDown(int[] arr, int parent, int end){
        int child = parent * 2 + 1;
        while (child < end){
            if (child + 1 < end)
                child = arr[child] > arr[child +1] ? child : child + 1;
            if (arr[child] > arr[parent]){
                int tmp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }

    /**
     * 5.冒泡排序
     * 时间的复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * 对数据不敏感
     */
    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length; i++){
            boolean flg = true;
            for (int j = 0; j < arr.length - 1 - i; j++){
                if (arr[j] > arr[j + 1]){
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flg = false;
                }
            }
            if (flg) break;
        }
    }


    /**
     * 6.快速排序
     * 时间复杂度：O(nlogN)[最好的情况了] O(n^2)[数据是有序地，或者是逆序的]
     * 空间复杂度：O(logN)[好的情况] O(N)[不好的情况]
     * 稳定性：不稳定的
     * 找基准使用顺序：挖坑法，hoare法，前后指针法
     */
    //递归
    public static void quickSort(int[] arr){
        quick(arr, 0, arr.length - 1);
    }
    private static void quick(int[] arr, int start, int end){
        if (start >= end) return;
        //范围优化
        if (end - start + 1 <= 20){
            insertSort1(arr, start, end);
            return;
        }
        //
        //三数取中优化
        int mid = threeNum(arr, start, end);
        int tmp = arr[start];
        arr[start] = arr[mid];
        arr[mid] = tmp;
        //
        int pivot = getPivot1(arr,start, end);
        quick(arr, start,pivot - 1);
        quick(arr, pivot + 1, end);
    }
    //非递归
    public static void quickSort1(int[] arr){
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        int end = arr.length - 1;

        stack.push(start);
        stack.push(end);
        while (!stack.empty()){
            //范围优化
            if (end - start + 1 <= 20){
                insertSort1(arr, start, end);
            }

            //三数取中优化
            int mid = threeNum(arr, start, end);
            int tmp = arr[start];
            arr[start] = arr[mid];
            arr[mid] = tmp;
            //
            int pivot = getPivot(arr, start, end);
            if (pivot > start + 1){
                stack.push(start);
                stack.push(pivot -  1);
            }
            if (pivot < end - 1){
                stack.push(pivot + 1);
                stack.push(end);
            }
            end = stack.pop();
            start = stack.pop();
        }
    }
    //三数取中法优化
    private static int threeNum(int[] arr, int left, int right){
        int mid = (left + right) / 2;
        if (arr[left] < arr[right]){
            if (arr[mid] < arr[left]) return left;
            else if (arr[mid] > arr[right]) return right;
            else return mid;
        }else{
            if (arr[mid] > arr[left]) return left;
            else if (arr[mid] < arr[right]) return right;
            else return mid;
        }
    }
    private static void insertSort1(int[] arr,int start, int end){
        for  (int i = start + 1; i <= end; i++){
            int j = i - 1;
            int tmp = arr[i];
            for (;j >= 0;j--){
                if (arr[j] > tmp)
                    arr[j + 1] = arr[j];
                else
                    break;
            }
            arr[j + 1] = tmp;
        }
    }

    //hoare法找基准
    private static int getPivot(int[] arr, int left, int right){
        int i = left;
        int key = arr[left];
        while (left < right){
            while (left < right && arr[right] >= key) right--;
            while (left < right && arr[left] <= key) left++;
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
        }
        int tmp = arr[left];
        arr[left] = arr[i];
        arr[i] = tmp;
        return left;
    }
    //挖坑法找基准
    private static int getPivot1(int[] arr, int left, int right){
        int key = arr[left];
        while (left < right){
            while (left < right && arr[right] >= key) right--;
            arr[left] = arr[right];
            while (left < right  && arr[left] <= key) left++;
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }
    //前后指针法着基准
    private static int getPivot2(int[] arr, int left, int right){
        int prev = left;
        int cur = left + 1;
        while (cur <= right){
            if (arr[left] > arr[cur] && arr[++prev] != arr[cur]){
                int tmp = arr[prev];
                arr[prev] = arr[cur];
                arr[cur] = tmp;
            }
            cur++;
        }
        int tmp = arr[prev];
        arr[prev] = arr[left];
        arr[left] = tmp;
        return prev;
    }

    /**
     * 7.归并排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(N)
     * 稳定性：稳定的
     * @param arr
     */
    //递归方法
    public static void mergeSort(int[] arr){
        mergeFunc(arr,0,arr.length - 1);
    }
    public static void mergeFunc(int[] arr,int left, int right){
        if (left >= right) return;
        int mid = (left + right) / 2;
        mergeFunc(arr,left,mid);
        mergeFunc(arr,mid + 1, right);
        merge(arr, left, mid, right);
    }
    public static void merge(int[] arr,int left, int mid, int right){
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int k = 0;
        int[] arr1 = new int[right - left + 1];
        while (s1 <= e1 && s2 <= e2) {
            if (arr[s1] <= arr[s2]) arr1[k++] = arr[s1++];
            else arr1[k++] = arr[s2++];
        }
        while (s1 <= e1) arr1[k++] = arr[s1++];
        while (s2 <= e2) arr1[k++] = arr[s2++];
        for (int i = 0; i < k; i++) arr[i + left] = arr1[i];
    }
    //非递归
    public static void mergeSort1(int[] arr){
        for (int gap = 1; gap < arr.length; gap *= 2){
            for (int i = 0; i < arr.length; i += gap * 2){
                int left = i;
                int mid = i + gap - 1;
                int right = mid + gap;
                if (mid >= arr.length) mid = arr.length - 1;
                if (right >= arr.length) right = arr.length - 1;
                merge(arr, left, mid, right);
            }
        }
    }

    /**
     * 计数排序
     * 时间复杂度O(范围+n)
     * 空间复杂度O(范围)
     * 稳定性：稳定
     */
    public static void countArray(int[] arr){
        int min = arr[0];
        int max = arr[0];
        for(int x: arr){
            if (x < min) min = x;
            if (x > max) max = x;
        }
        int[] ret = new int[max - min + 1];
        for (int x:arr){
            ret[x - min]++;
        }
        int index = 0;
        for (int i = 0; i < ret.length; i++){
            for (int j = 0; j < ret[i]; j++){
                arr[index++] = i + min;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = { 7,8,1,23,1,2,54,123 };
        quickSort1(arr);
        System.out.println(Arrays.toString(arr));
    }


}
